

class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode deleteNode1(ListNode head, int val) {
        if (val == head.val) {
            return head.next;
        }
        ListNode curr = head;
        while (curr.next != null) {
            if (curr.next.next == null) {
                curr.next = null;
                return head;
            }
            if (curr.next.val == val) {
                curr.next = curr.next.next;
                return head;
            }
            curr = curr.next;
        }
        return head;
    }

    public ListNode deleteNode2(ListNode head, int val) {
        if (val == head.val) return head.next;
        ListNode prev = head, curr = head.next;
        while (curr != null && curr.val != val) {
            prev = curr;
            curr = curr.next;
        }
        if (curr != null) prev.next = curr.next;
        return head;
    }

    public ListNode getKthFromEnd1(ListNode head, int k) {
        ListNode cur = head, pre = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int pos = len - k;
        for (int i = 0; i < pos; i++) {
            pre = pre.next;
        }
        return pre;
    }

    public ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode former = head, latter = head;
        for (int i = 0; i < k; i++) {
            former = former.next;
        }
        while (former != null) {
            latter = latter.next;
            former = former.next;
        }
        return latter;
    }

    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return head.next;
    }

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l2.next, l1);
            return l2;
        }
    }

    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode head1 = headA;
        ListNode head2 = headB;
        while (head1 != null && head2 != null) {
            head1 = head1.next;
            head2 = head2.next;
        }
        while (head1 != null) {
            head1 = head1.next;
            headA = headA.next;
        }
        while (head2 != null) {
            head2 = head2.next;
            headB = headB.next;
        }
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headB;
    }

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
    
}